//
// Created by Criinal Nicole on 2021/5/7.
//

#ifndef GFD_VF2_H
#define GFD_VF2_H

#include <cassert>
#include "../dataStructure/Graph.h"
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <utility>


class VF2 {
public:
    Graph dataGraph, queryGraph;

    VF2(Graph queryGraph, Graph dataGraph);

//    预处理：生成候选集
    bool generateCandidateSet(std::map<int, std::set<int>> &candidateSet,
                              std::set<int> matchedVertex = {});

//    比较候选集的大小，并更新retVertex
    static void updateRetVertex(std::map<int, std::set<int>> &candidateSet,
                                int &retVertex,
                                int &vertex);

//    获取pattern中需要匹配的下一个点
    int getNextVertex(std::map<int, std::set<int>> &candidateSet,
                      std::map<int, int> &matchState);

//    检查edges数组中是否存在下标对应的边
//    传入-1表示不检查该参数
//    如果检查到则将当前边的下标加入checkedEdge中（为了检查重边）
    static bool checkEdgeById(const std::vector<Edge> &edges,
                              int from,
                              int to,
                              int label,
                              std::set<int> &checkedEdge);

//    检查edges数组中是否存在下标对应的边
//    传入-1表示不检查该参数
    static bool checkEdgeById(const std::vector<Edge> &edges,
                              int from,
                              int to,
                              int label);

//    检查两个点是否能匹配上
//    能则加入matchState中
    static bool isJoinable(Vertex &targetVertex,
                           Vertex &queryVertex,
                           std::map<int, int> &matchState);

//    更新matchState的状态
//    将(queryVertex, targetVertex)加入matchState
//    并将matchedVertex中targetVertex的状态设置成true
    static void updateState(int queryVertex,
                            int targetVertex,
                            std::map<int, int> &matchState,
                            std::set<int> &matchedVertex);

//    更新matchState的状态
//    将(queryVertex, targetVertex)从matchState中删除
//    并将matchedVertex中targetVertex的状态设置成false
    static void restoreState(int queryVertex,
                             int targetVertex,
                             std::map<int, int> &matchState,
                             std::set<int> &matchedVertex
    );

//    检查edges数组中是否存在标签对应的边
//    传入-1表示不检查该参数
    static bool checkEdgeByLabel(Graph &graph,
                                 const std::vector<Edge> &edges,
                                 int fromLabel,
                                 int toLabel,
                                 int edgeLabel);

//    单向地更新候选集 将不匹配的点从候选集中删去
//    可选择更新出边/入边
    static bool updateCandidateOneDirection(EdgeState edgeState,
                                            std::vector<Edge> &queryEdges,
                                            std::vector<Edge> &targetEdges,
                                            std::map<int, std::set<int>> &candidateSet,
                                            std::map<int, int> &matchState,
                                            std::set<int> &matchedVertex);

//    更新候选集 将不匹配的点从候选集中删去
//    调用两次updateCandidateOneDirection
    static bool updateCandidateSet(Vertex &queryVertex,
                                   Vertex &targetVertex,
                                   std::map<int, std::set<int>> &candidateSet,
                                   std::map<int, int> &matchState,
                                   std::set<int> &matchedVertex);

//    VF2的搜索主体
    template<typename MatchCallback, typename PruneCallback>
    bool vf2Search(std::map<int, std::set<int>> &candidateSet,
                   std::map<int, int> &matchState,
                   std::set<int> &matchedVertex,
                   int &resultCount,
                   MatchCallback matchCallback,
                   PruneCallback pruneCallback);

//    不带matchState的匹配
    template<typename MatchCallback, typename PruneCallback>
    bool vf2Engine(MatchCallback matchCallback,
                   PruneCallback pruneCallback);

//    带matchState的匹配
    template<typename MatchCallback, typename PruneCallback>
    bool vf2Engine(MatchCallback matchCallback,
                   PruneCallback pruneCallback,
                   std::map<int, int> matchState);

//    通过matchState获取dataGraph中已匹配的点
    static std::set<int> generateMatchedVertex(std::map<int, int> &matchState);


};

VF2::VF2(Graph query, Graph data) {
    dataGraph = std::move(data);
    queryGraph = std::move(query);
}

bool VF2::generateCandidateSet(std::map<int, std::set<int>> &candidateSet,
                               std::set<int> matchedVertex) {
    for (int i = 0; i < queryGraph.size(); ++i) {
//        if (matchedVertex.find(i) != matchedVertex.end())continue;
        const auto &queryVertex = queryGraph[i];
        std::set<int> tmpCandidateSet{};
        for (int j = 0; j < dataGraph.size(); ++j) {
            const auto &vertex = dataGraph[j];
            if (queryVertex.labelEqual(vertex) &&
                vertex.outEdges.size() >= queryVertex.outEdges.size() &&
                vertex.inEdges.size() >= queryVertex.inEdges.size())
                tmpCandidateSet.insert(j);
        }
        if (tmpCandidateSet.empty()) {
            candidateSet.clear();
            return false;
        }
        candidateSet.insert(make_pair(i, tmpCandidateSet));
    }
    return true;
}

void VF2::updateRetVertex(std::map<int, std::set<int>> &candidateSet,
                          int &retVertex,
                          int &vertex) {
    if (retVertex == -1 ||
        candidateSet[retVertex].size() > candidateSet[vertex].size())
        retVertex = vertex;
}

int VF2::getNextVertex(std::map<int, std::set<int>> &candidateSet,
                       std::map<int, int> &matchState) {

//    检查与现有match点相连并未匹配的点
    int retVertex{-1};
    for (const auto &vertexPair : matchState) {
        auto &matchedVertex = queryGraph.at(vertexPair.first);
        for (const auto &edge : matchedVertex.inEdges) {
            auto vertex = edge.getFromVertex();
            if (matchState.find(vertex) != matchState.end()) continue;
            updateRetVertex(candidateSet, retVertex, vertex);
        }
        for (const auto &edge : matchedVertex.outEdges) {
            auto vertex = edge.getToVertex();
            if (matchState.find(vertex) != matchState.end()) continue;
            updateRetVertex(candidateSet, retVertex, vertex);
        }

    }

//    第一次检查 matchState为空
//    或者未找到结果 考虑有多个弱连通分量，此时将检查所有未匹配的点
    if (retVertex == -1) {
        for (int vertex = 0; vertex < queryGraph.size(); ++vertex) {
            if (matchState.find(vertex) != matchState.end())continue;
            updateRetVertex(candidateSet, retVertex, vertex);
        }
    }
//    assert(retVertex >= 0);
//    assert(retVertex < queryGraph.size());
    return retVertex;
}

bool VF2::checkEdgeById(const std::vector<Edge> &edges,
                        const int from,
                        const int to,
                        const int label,
                        std::set<int> &checkedEdge) {
    for (int i = 0; i < edges.size(); ++i) {
        if (checkedEdge.find(i) != checkedEdge.end())continue;
        const auto &edge = edges[i];
        if (label != -1 && edge.getLabel() != label)continue;
        if (to != -1 && edge.getToVertex() != to)continue;
        if (from != -1 && edge.getFromVertex() != from) continue;
        checkedEdge.insert(i);
        return true;
    }
    return false;
}

bool VF2::checkEdgeById(const std::vector<Edge> &edges,
                        const int from,
                        const int to,
                        const int label) {
    for (const auto &edge : edges) {
        if (label != -1 && edge.getLabel() != label)continue;
        if (to != -1 && edge.getToVertex() != to)continue;
        if (from != -1 && edge.getFromVertex() != from) continue;
        return true;
    }
    return false;
}

bool VF2::isJoinable(Vertex &targetVertex,
                     Vertex &queryVertex,
                     std::map<int, int> &matchState) {
    std::set<int> checkedEdge{};
//    检查入边
    for (const auto &queryEdge : queryVertex.inEdges) {
        auto checkVertex = queryEdge.getFromVertex();
        if (matchState.find(checkVertex) == matchState.end())continue;
        if (!checkEdgeById(targetVertex.inEdges,
                           matchState[checkVertex],
                           -1,
                           queryEdge.getLabel(),
                           checkedEdge)) {
            return false;
        }
    }
    checkedEdge.clear();
//    检查出边
    for (const auto &queryEdge : queryVertex.outEdges) {
        auto checkVertex = queryEdge.getToVertex();
        if (matchState.find(checkVertex) == matchState.end())continue;
        if (!checkEdgeById(targetVertex.outEdges,
                           -1,
                           matchState[checkVertex],
                           queryEdge.getLabel(),
                           checkedEdge)) {
            return false;
        }
    }
    return true;
}

void VF2::updateState(int queryVertex,
                      int targetVertex,
                      std::map<int, int> &matchState,
                      std::set<int> &matchedVertex) {
    matchState.insert(std::make_pair(queryVertex, targetVertex));
    matchedVertex.insert(targetVertex);
}

void VF2::restoreState(int queryVertex,
                       int targetVertex,
                       std::map<int, int> &matchState,
                       std::set<int> &matchedVertex) {
    matchState.erase(queryVertex);
    matchedVertex.erase(targetVertex);
}

bool VF2::checkEdgeByLabel(Graph &graph,
                           const std::vector<Edge> &edges,
                           const int fromLabel,
                           const int toLabel,
                           const int edgeLabel) {
    for (const auto &edge : edges) {
        if (edgeLabel != -1 && edge.getLabel() != edgeLabel)continue;
        if (toLabel != -1 && graph[edge.getToVertex()].getLabel() != toLabel)continue;
        if (fromLabel != -1 && graph[edge.getFromVertex()].getLabel() != fromLabel) continue;
        return true;
    }
    return false;
}

bool VF2::updateCandidateOneDirection(EdgeState edgeState,
                                      std::vector<Edge> &queryEdges,
                                      std::vector<Edge> &targetEdges,
                                      std::map<int, std::set<int>> &candidateSet,
                                      std::map<int, int> &matchState,
                                      std::set<int> &matchedVertex) {
    for (auto &queryEdge: queryEdges) {
        auto adjQueryVertex = (edgeState == EdgeState::in)
                              ? queryEdge.getFromVertex()
                              : queryEdge.getToVertex();

        if (matchState.find(adjQueryVertex) != matchState.end())continue;

        std::set<int> tmpSet = candidateSet[adjQueryVertex];
        for (auto &adjTargetVertex :tmpSet) {
            if (matchedVertex.find(adjTargetVertex) != matchedVertex.end())continue;

            auto from = (edgeState == EdgeState::in) ? adjTargetVertex
                                                     : -1;
            auto to = (edgeState == EdgeState::in) ? -1
                                                   : adjTargetVertex;

            if (!checkEdgeById(targetEdges, from, to, queryEdge.getLabel())) {
                candidateSet[adjQueryVertex].erase(adjTargetVertex);
                continue;
            }
        }
    }
    return true;
}

bool VF2::updateCandidateSet(Vertex &queryVertex,
                             Vertex &targetVertex,
                             std::map<int, std::set<int>> &candidateSet,
                             std::map<int, int> &matchState,
                             std::set<int> &matchedVertex) {
    updateCandidateOneDirection(EdgeState::in,
                                queryVertex.inEdges,
                                targetVertex.inEdges,
                                candidateSet,
                                matchState,
                                matchedVertex);

    updateCandidateOneDirection(EdgeState::out,
                                queryVertex.outEdges,
                                targetVertex.outEdges,
                                candidateSet,
                                matchState,
                                matchedVertex);
    return true;
}

template<typename MatchCallback, typename PruneCallback>
bool VF2::vf2Search(std::map<int, std::set<int>> &candidateSet,
                    std::map<int, int> &matchState,
                    std::set<int> &matchedVertex,
                    int &resultCount,
                    MatchCallback matchCallback,
                    PruneCallback pruneCallback) {
    if (queryGraph.empty() || dataGraph.empty()) {
        return matchCallback(matchState);
    }

//    剪枝
    if (pruneCallback(matchState))return true;
//    已经匹配到答案
    if (matchState.size() == candidateSet.size()) {
        return matchCallback(matchState);
    }


//    找出下一个需要匹配的pattern上的点
    auto nextQueryVertex = getNextVertex(candidateSet,
                                         matchState);
    if (nextQueryVertex == -1)return false;
    for (const auto &nextTargetVertex: candidateSet.find(nextQueryVertex)->second) {
        if (pruneCallback(matchState))return true;
        if (matchedVertex.find(nextTargetVertex) != matchedVertex.end())continue;
        if (isJoinable(dataGraph[nextTargetVertex],
                       queryGraph[nextQueryVertex],
                       matchState)) {
            updateState(nextQueryVertex,
                        nextTargetVertex,
                        matchState,
                        matchedVertex);
            auto tempCandidateSet = candidateSet;
            if (!updateCandidateSet(queryGraph[nextQueryVertex],
                                    dataGraph[nextTargetVertex],
                                    tempCandidateSet,
                                    matchState,
                                    matchedVertex))
                continue;
            if (!vf2Search(tempCandidateSet,
                           matchState,
                           matchedVertex,
                           resultCount,
                           matchCallback,
                           pruneCallback))
                return false;
            restoreState(nextQueryVertex,
                         nextTargetVertex,
                         matchState,
                         matchedVertex);
        }
    }
    return true;
}

template<typename MatchCallback, typename PruneCallback>
bool VF2::vf2Engine(MatchCallback matchCallback,
                    PruneCallback pruneCallback) {
    std::map<int, std::set<int>> candidateSet{};
    if (!generateCandidateSet(candidateSet)) {
        return false;
    }
    std::set<int> matchedVertex;
    std::map<int, int> matchState;
    int resultCount = 0;
    vf2Search(candidateSet,
              matchState,
              matchedVertex,
              resultCount,
              matchCallback,
              pruneCallback);
    return true;
}

std::set<int> VF2::generateMatchedVertex(std::map<int, int> &matchState) {
    std::set<int> retSet;
    for (auto &matchPair:matchState) {
        retSet.insert(matchPair.second);
    }
    return retSet;
}

template<typename MatchCallback, typename PruneCallback>
bool VF2::vf2Engine(MatchCallback matchCallback,
                    PruneCallback pruneCallback,
                    std::map<int, int> matchState) {
    std::map<int, std::set<int>> candidateSet{};
    std::set<int> matchedVertex = generateMatchedVertex(matchState);
    if (!generateCandidateSet(candidateSet)) {
        return false;
    }
    int resultCount = 0;
    vf2Search(candidateSet,
              matchState,
              matchedVertex,
              resultCount,
              matchCallback,
              pruneCallback);
    return true;
}

#endif //GFD_VF2_H
